//给你两棵二叉树： root1 和 root2 。 
//
// 想象一下，当你将其中一棵覆盖到另一棵之上时，两棵树上的一些节点将会重叠（而另一些不会）。你需要将这两棵树合并成一棵新二叉树。合并的规则是：如果两个节点重叠
//，那么将这两个节点的值相加作为合并后节点的新值；否则，不为 null 的节点将直接作为新二叉树的节点。 
//
// 返回合并后的二叉树。 
//
// 注意: 合并过程必须从两个树的根节点开始。 
//
// 
//
// 示例 1： 
//
// 
//输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
//输出：[3,4,5,5,4,null,7]
// 
//
// 示例 2： 
//
// 
//输入：root1 = [1], root2 = [1,2]
//输出：[2,2]
// 
//
// 
//
// 提示： 
//
// 
// 两棵树中的节点数目在范围 [0, 2000] 内 
// -10⁴ <= Node.val <= 10⁴ 
// 
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 928 👎 0

package leetcode.editor.cn;

import java.util.LinkedList;
import java.util.Queue;

class MergeTwoBinaryTrees {
    public static void main(String[] args) {
        Solution solution = new MergeTwoBinaryTrees().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
//        /**
//         * 递归法（前序）
//         * @param root1
//         * @param root2
//         * @return
//         */
//        public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        // 为空直接返回一个节点即可，不用在递归
//            if (root1 == null) return root2;
//            if (root2 == null) return root1;
//
//            root1.val += root2.val; // 将root1作为结果，节约资源，中
//            root1.left = mergeTrees(root1.left, root2.left);
//            root1.right = mergeTrees(root1.right, root2.right);
//
//            return root1;
//        }

//        /**
//         * 递归法（中序）
//         *
//         * @param root1
//         * @param root2
//         * @return
//         */
//        public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
//            // 为空直接返回一个节点即可，不用在递归
//            if (root1 == null) return root2;
//            if (root2 == null) return root1;
//
//            root1.left = mergeTrees(root1.left, root2.left);    // 左
//            root1.val += root2.val; // 将root1作为结果，节约资源，中
//            root1.right = mergeTrees(root1.right, root2.right); // 右
//
//            return root1;
//        }
//        /**
//         * 递归法（中序）
//         *
//         * @param root1
//         * @param root2
//         * @return
//         */
//        public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
//            // 为空直接返回一个节点即可，不用在递归
//            if (root1 == null) return root2;
//            if (root2 == null) return root1;
//
//            root1.left = mergeTrees(root1.left, root2.left);    // 左
//            root1.right = mergeTrees(root1.right, root2.right); // 右
//            root1.val += root2.val; // 将root1作为结果，节约资源，中
//
//            return root1;
//        }

        /**
         * 迭代法
         *
         * @param root1
         * @param root2
         * @return
         */
        /*public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
            // 判断2棵树第一个元素
            if (root1 == null) return root2;
            if (root2 == null) return root1;
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root1);
            queue.offer(root2);

            while (!queue.isEmpty()) {
                TreeNode node1 = queue.poll();
                TreeNode node2 = queue.poll();

                node1.val += node2.val; // 此时2个节点一定不为null

                // 如果2个节点的左节点都不为空，那么都加入节点
                if (node1.left != null && node2.left != null) {
                    queue.offer(node1.left);
                    queue.offer(node2.left);
                }

                // 如果2个节点的右节点都不为空，那么都加入节点
                if (node1.right != null && node2.right != null) {
                    queue.offer(node1.right);
                    queue.offer(node2.right);
                }

                // 当t1的左节点 为空 t2左节点不为空，就赋值过去
                if (node1.left == null && node2.left != null) {
                    node1.left = node2.left;
                }

                // 当t1的右节点 为空 t2右节点不为空，就赋值过去
                if (node1.right == null && node2.right != null) {
                    node1.right = node2.right;
                }

                // 如果左节点为空，右节点不为空的话，因为最后以root1作为返回结果，所以不需要在进行判断
            }
            return root1;
        }*/

        // 递归法，操作一个树就是合并成一棵树
        /*public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
            if (root1 == null) return root2;
            if (root2 == null) return root1;
            root1.val += root2.val;
            root1.left = mergeTrees(root1.left, root2.left);
            root1.right = mergeTrees(root1.right, root2.right);
            return root1;
        }*/

        // 迭代法（层序遍历）
        /*public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root1);
            queue.offer(root2);
            while (!queue.isEmpty()) {
                TreeNode node1 = queue.poll();
                TreeNode node2 = queue.poll();
                node1.val += node2.val;

                if (node1.left != null && node2.left != null) {
                    queue.offer(node1.left);
                    queue.offer(node2.left);
                }

                if (node1.right != null && node2.right != null) {
                    queue.offer(node1.right);
                    queue.offer(node2.right);
                }

                if (node1.left == null && node2.left != null) {
                    node1.left = node2.left;
                }

                if (node1.right == null && node2.right != null) {
                    node1.right = node2.right;
                }
            }
            return root1;
        }*/
        public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
            if (root1 == null && root2 == null) return null;
            if (root1 == null) return root2;
            else if (root2 == null) return root1;
            else root1.val += root2.val;
            root1.left = mergeTrees(root1.left, root2.left);
            root1.right = mergeTrees(root1.right, root2.right);
            return root1;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
